// 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

// 暴露接口
function findSubsequences(nums: number[]): number[][] {
  const res: number[][] = []; // 结果数组
  const hashSet = new Set<string>();// 哈希集合
  findSubsequences_DFS(nums, res, 0, [], hashSet);
  return res;
}

function findSubsequences_DFS(
  nums: number[],
  res: number[][],
  index: number,
  path: number[],
  hashSet: Set<string>
) {
  const hashkey = path.join(".");// 拼接出hashkey
  if (path.length > 1 && !hashSet.has(hashkey)) {// 出口检测，如果路径长度大于1且未重复那就加入结果数组
    res.push(Array.from(path));
    hashSet.add(hashkey);
  }
  for (let i = index; i < nums.length; i++) {
      // 注意！if的判断条件，当路径为空或者当前数字小于路径末尾元素就直接把当前元素加入路径中
    if (path.length === 0 || nums[i] >= path[path.length - 1]) {
      path.push(nums[i]);
      findSubsequences_DFS(nums, res, i + 1, path, hashSet);
      path.pop();// 注意！！path是引用，路径走完之后防止路径元素重复要撤销当前加入的元素
    }
  }
}


// 这道题目的考点在于是使用深度优先搜索和循环结合
// 宏观上循环加递归并不是很好理解，建议一定要画出树状图来结合本题目进行理解
// 首先我们思考这么一个问题，那就是这道题找的是子数组的递增序列
// 那么数组中的每个根元素都是可以用来做根节点的，确定了这点我们可以得到大的框架一定是在一个循环下
// 通过循环我们可以拿到根节点，我们要找根节点组成的各种可能组合，而且剩余的组合元素是和其他几个数组元素相关
// 理论上要把所有的递增序列找全，我们是应该找到最长的递增序列，这个找最长的过程是可以用深度优先搜索实现的
// 这里我们就可以得到题目大的框架应该是介于使用循环遍历结合深度优先搜索的方式
// 下面思考几个关键点：
// 1. 找最长的过程，路径内的数组元素是一个一个的增加的，只要当前的路径元素数量大于1，它
// 就是一个子数组，我们就应该把它加入结果数组当中。
// 2. 题目中给定的参数是可能出现重复的，意味着结果数组也可能出现重复，这里为了方便代码理解引入一个hashSet来做去重的工作
// 我们可以使用数组用','拼接出一个字符串来做唯一的hashKey
// 3. 思考什么时候可以加当前元素加入路径中，比较容易想到的是当前元素大于数组的末尾元素时可以把当前元素直接加入路径，
// 但还要注意的情况时当路径为空的时候说明这里存在的是一个根节点，可以直接把根节点加入路径数组当中。
// 4. 在代码运行的过程中我们传递的是path数组的引用，深度优先搜索完成之后路径的数组元素是存在之前元素的记录的，
// 所以在完成深度优先搜索后需要撤销当前的元素
// 根据以上写出代码即可。


